package com.company.Graph.Kruskal;


import java.awt.image.AreaAveragingScaleFilter;
import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}11:00
 */
public class KruskalClass {
    private int edgeNum;// 边的个数
    private char[] vertexs;// 顶点数组
    private int[][] matrix;// 邻接矩阵
    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        char[] vertexs = {'A','B','C','D','E','F','G'};
        // 邻接矩阵
        int matrix[][] = {
                {0,12,INF,INF,INF,16,14},
                {12,0,10,INF,INF,7,INF},
                {INF,10,0,3,5,5,INF},
                {INF,INF,3,0,4,INF,INF},
                {INF,INF,5,4,0,2,8},
                {16,7,6,INF,2,0,9},
                {14,INF,INF,INF,8,9,0}
        };
        KruskalClass aClass = new KruskalClass(vertexs, matrix);
        EData[] eData = aClass.getEdges();
        aClass.sortEdges(eData);
        System.out.println(Arrays.toString(eData));
        aClass.kruskal();
    }

    // 构造器

    public KruskalClass(char[] vertexs, int[][] matrix) {
        int vlen = vertexs.length;

        // 初始化顶点
        this.vertexs = new char[vlen];
        for (int i = 0; i < vertexs.length; i++){
            this.vertexs[i] = vertexs[i];
        }
        this.matrix = matrix;

        // 统计边
        for (int i = 0; i < vlen; i++){
            for (int j = i + 1; j < vlen; j++){
                if (this.matrix[i][j] != INF){// 这里把0也统计进去了的
                    edgeNum++;
                }
            }
        }
    }

    // 打印邻接矩阵
    public  void print(){
        System.out.println("邻接矩阵为：");
        for (int i = 0; i < vertexs.length; i++){
            for (int j = 0 ; j < vertexs.length; j++){
                System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }
    }
    // 对边进行一个排序处理，冒泡排序
    private void sortEdges(EData[] eData){
        for (int i = 0; i < eData.length - 1; i++){
            for (int j = 0; j < eData.length - 1 - i; j++){
                if (eData[j].weight > eData[j + 1].weight){// 交换
                    EData temp = eData[j];
                    eData[j] = eData[j + 1];
                    eData[j + 1] = temp;
                }
            }
        }
    }

    /**
     *
     * @param ch 表示顶点的值，比如'A' 'B'
     * @return
     */
    private int getPosition(char ch){
        for (int i = 0; i < vertexs.length; i++){
            if (vertexs[i] == ch){
                return i;
            }
        }
        // 如果找不到就返回-1;
        return -1;
    }

    // 获取图中的边，放到EData数组中，后面我们还需要遍历该数组
    // 通过matrix邻接矩阵来获取
    private EData[] getEdges(){
        int index = 0;
        EData[] edges = new EData[edgeNum];
        for (int i = 0; i < vertexs.length; i++){
            for (int j = i + 1; j < vertexs.length; j++){
                if (matrix[i][j] != INF){
                    edges[index++] = new EData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }
        return edges;
    }

    //
    /**
     * 获取下标为i的顶点的终点，用于后面判断两个顶点的终点是否相同
     * @param ends 数组记录了各个顶点对应的终点是哪个，类似并查集的用法
     * @param i
     * @return 返回的就是下标为i的这个顶点对应终点的下标
     */
    private int getEnd(int[] ends,int i){
        while (ends[i] != 0){
            i = ends[i];
        }
        return i;
    }

    public void kruskal(){
        int index = 0;// 表示最后结果数组的索引
        int[] ends = new int[edgeNum];// 用于保存“已有最小生成树”中的每个顶点在最小生成树中的终点
        // 创建结果数组，保存最后的最小生成树
        EData[] rets = new EData[edgeNum];

        // 获取图中所有的边的集合,一共有12条边
        EData[] edges = getEdges();
        System.out.println("有边" + Arrays.toString(edges));

        // 按照边的权值来进行排序
        sortEdges(edges);

        // 遍历edges数组 将边添加到最小生成树中时，判断准备加入的边是否形成回路，如果没有就加入到rets
        for (int i = 0; i < edgeNum; i++){
            // 获取到第i条边的第一个顶点
            int p1 = getPosition(edges[i].start);
            // 获取到第i条边的第2个顶点
            int p2 = getPosition(edges[i].end);

            // 获取p1这个顶点在已有最小生成树中的终点
            int m = getEnd(ends,p1);
            int n = getEnd(ends,p2);
            // 是否构成回路
            if (m != n){// 没有构成回路
                ends[m] = n; // 设置m在已有最小生成树的终点 并查集
                rets[index++] = edges[i]; // 有一条边加入到rets数组
            }
        }

        System.out.println(Arrays.toString(rets));
    }

}

class EData{
    char start;// 边的起点
    char end; // 边的终点
    int weight; // 边的权值
    // 构造器

    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
    // 重写toString方法 输出边
    @Override
    public String toString() {
        return "EData{" +
                "start=" + start +
                "-> end=" + end +
                ", weight=" + weight +
                '}'+'\n' ;
    }
}
